package divide;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 *
 *  双指针依次合并    分治合并两两合并     堆排序合并
 */
public class 合并K个排序链表_23 {

    /**
     * 法一  ：依次合并  两个两个来
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode cur = lists[0];
        for (int i = 1; i < lists.length; i++) {
            cur = merge2Lists(cur, lists[i]);
        }
        return cur;
    }

    /**
     * 法二  ：分治法合并
     *
     * @param lists
     * @return
     */
    public ListNode mergeKLists_devide(ListNode[] lists) {
        return merge(lists, 0, lists.length - 1);
    }

    /**
     * merge 包裹在 merge2Lists 外部 用于分治划分
     * 这种使用双函数进行分治递归的方式值得学习
     */
    private ListNode merge(ListNode[] lists, int start, int end) {
        if (start > end) return null;
        if (start == end) return lists[start];
        final int mid = (start + end) >> 1;
        return merge2Lists(merge(lists, start, mid), merge(lists, mid + 1, end));
    }

    public ListNode merge2Lists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        ListNode head = new ListNode(), tail = head;
        ListNode cur1 = l1, cur2 = l2;
        while (cur1 != null && cur2 != null) {
            if (cur1.val < cur2.val) {
                tail.next = cur1;
                cur1 = cur1.next;
            } else {
                tail.next = cur2;
                cur2 = cur1.next;
            }
            tail = tail.next;
        }
        tail.next = cur1 == null ? cur2 : cur1;
        return head.next;
    }

    public ListNode mergeKLists_heap(ListNode[] lists) {
        Queue<ListNode> queue = new PriorityQueue<>(Comparator.comparingInt(a -> a.val));
        for(ListNode head : lists) {
            if(head != null)
                queue.offer(head);
        }
        ListNode head = new ListNode();
        ListNode cur = head;
        while(!queue.isEmpty()) {
            cur.next = queue.poll();
            cur = cur.next;
            if(cur.next != null)
                queue.offer(cur.next);

        }
        return head.next;
    }


    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}
